package com.c2b.algorithm.leetcode.base;

import java.util.HashSet;
import java.util.Set;

/**
 * <a href='https://leetcode.cn/problems/path-crossing/'>判断路径是否相交(Path Crossing)</a>
 * <p>给你一个字符串 path，其中 path[i] 的值可以是 'N'、'S'、'E' 或者 'W'，分别表示向北、向南、向东、向西移动一个单位。</p>
 * <p>你从二维平面上的原点 (0, 0) 处开始出发，按 path 所指示的路径行走。</p>
 * <p>如果路径在任何位置上与自身相交，也就是走到之前已经走过的位置，请返回 true ；否则，返回 false 。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：path = "NES"
 *      输出：false
 *      解释：该路径没有在任何位置相交。
 *
 * 示例 2：
 *      输入：path = "NESWW"
 *      输出：true
 *      解释：该路径经过原点两次。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>1 <= path.length <= 10^4</li>
 *         <li>path[i] 为 'N'、'S'、'E' 或 'W'</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/12/20 14:27
 */
public class LC1496PathCrossing_S {

    static class Solution {
        public boolean isPathCrossing(String path) {
            Set<String> visited = new HashSet<>();
            int x = 0;
            int y = 0;
            for (char ch : path.toCharArray()) {
                visited.add(x + " " + y);
                switch (ch) {
                    case 'N':
                        ++y;
                        break;
                    case 'S':
                        --y;
                        break;
                    case 'E':
                        ++x;
                        break;
                    case 'W':
                        --x;
                        break;
                }
                if (visited.contains(x + " " + y)) {
                    return true;
                }
            }
            return false;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.isPathCrossing("NES"));
        System.out.println(solution.isPathCrossing("NESWW"));
        System.out.println(solution.isPathCrossing("SN"));
        System.out.println(solution.isPathCrossing("W"));
    }
}
